{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "confirmed-bargain",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "smoking-basin",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1,2,3,4,5,6,7,8,9,10]\n",
    "y = [5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.9, 8.7, 9.0, 9.05]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "growing-posting",
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.DataFrame({'x':x, 'y':y})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "cellular-album",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>x</th>\n",
       "      <th>y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>5.56</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>5.70</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>5.91</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>6.40</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>6.80</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>6</td>\n",
       "      <td>7.05</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>7</td>\n",
       "      <td>8.90</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>8</td>\n",
       "      <td>8.70</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>9</td>\n",
       "      <td>9.00</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>10</td>\n",
       "      <td>9.05</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    x     y\n",
       "0   1  5.56\n",
       "1   2  5.70\n",
       "2   3  5.91\n",
       "3   4  6.40\n",
       "4   5  6.80\n",
       "5   6  7.05\n",
       "6   7  8.90\n",
       "7   8  8.70\n",
       "8   9  9.00\n",
       "9  10  9.05"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "looking-interview",
   "metadata": {},
   "source": [
    "按照前面算法第1步求$f_1(x)$即回归树$T_1(x)$\n",
    "首先通过优化以下优化问题\n",
    "$$\n",
    "    \\min_s \\left[ \\min_{c_1} \\sum_{x_i\\in R_1} \\left(y_i - c_1 \\right)^2 + \\min_{c_2}\\sum_{x_i\\in R_2}\\left(y_i - c_2 \\right)^2 \\right]\n",
    "$$\n",
    "求解训练数据的切分点$s$:\n",
    "\n",
    "$$\n",
    "R_{1} = \\left\\{  x | x \\leq s \\right\\}, R_{2} = \\left\\{  x | x \\gt s \\right\\}\n",
    "$$\n",
    "\n",
    "容易求得在$R_1$，$R_2$内部使平方损失误差值达到最小值的$c_1$，$c_2$为\n",
    "$$\n",
    "c_1 = \\frac{1}{N_1}\\sum_{x_i\\in R_1}y_i,\\space\\space\\space c_2 = \\frac{1}{N_2}\\sum_{x_i\\in R_2}y_i, \n",
    "$$\n",
    " 这里$N_1$，$N_2$是$R_1$，$R_2$的样本点数，求训练集切分点。根据所给数据，可以考虑如下切分点：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "executive-wrestling",
   "metadata": {},
   "outputs": [],
   "source": [
    "ss = [1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "strategic-warren",
   "metadata": {},
   "source": [
    "## 计算第一次分割点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "distributed-barrel",
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "figured-frontier",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0    5.56\n",
       "Name: y, dtype: float64"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df['y'][:i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "after-spare",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0    0.0\n",
       "Name: y, dtype: float64"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(df['y'][:i] - df['y'][:i].mean())**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "communist-monroe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1   -1.801111\n",
       "2   -1.591111\n",
       "3   -1.101111\n",
       "4   -0.701111\n",
       "5   -0.451111\n",
       "6    1.398889\n",
       "7    1.198889\n",
       "8    1.498889\n",
       "9    1.548889\n",
       "Name: y, dtype: float64"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df['y'][i:]-df['y'][i:].mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "silent-albany",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15.72308888888889"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((df['y'][i:]-df['y'][i:].mean())**2).sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "royal-midnight",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "分割点:1.5, 损失值:15.72308888888889\n",
      "分割点:2.5, 损失值:12.083387500000002\n",
      "分割点:3.5, 损失值:8.365638095238097\n",
      "分割点:4.5, 损失值:5.775475000000003\n",
      "分割点:5.5, 损失值:3.9113200000000017\n",
      "分割点:6.5, 损失值:1.9300083333333338\n",
      "分割点:7.5, 损失值:8.009809523809526\n",
      "分割点:8.5, 损失值:11.7354\n",
      "分割点:9.5, 损失值:15.7386\n"
     ]
    }
   ],
   "source": [
    "# 计算所有分割点对应的损失值\n",
    "for i in range(1, 10):\n",
    "    print('分割点:{}, 损失值:{}'.format(i+0.5, ((df['y'][:i] - df['y'][:i].mean())**2).sum() + ((df['y'][i:]-df['y'][i:].mean())**2).sum()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "super-remainder",
   "metadata": {},
   "source": [
    "\n",
    "当s=6.5时计算如下"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "latest-genesis",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0    5.56\n",
       "1    5.70\n",
       "2    5.91\n",
       "3    6.40\n",
       "4    6.80\n",
       "5    7.05\n",
       "Name: y, dtype: float64"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df['y'][:6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "involved-place",
   "metadata": {},
   "outputs": [],
   "source": [
    "c1 = df['y'][:6].mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "unnecessary-illness",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.236666666666667"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "exempt-congress",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.8581333333333332"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sum(np.power((df['y'][:6] - c1), 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "after-daisy",
   "metadata": {},
   "outputs": [],
   "source": [
    "c2 = df['y'][6:].mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "cultural-radius",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8.912500000000001"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "hungarian-italic",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0718750000000005"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sum(np.power((df['y'][6:] - c2), 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "comfortable-vancouver",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.9300083333333338"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sum(np.power((df['y'][:6] - c1), 2))+np.sum(np.power((df['y'][6:] - c2), 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "greenhouse-nature",
   "metadata": {},
   "source": [
    "s = 6.5 时 决策树损失值最小\n",
    "$$\n",
    "T_{1}(x) = \\begin{cases}\n",
    "6.24, &x<6.5 \\\\\n",
    "8.91, &x>=6.5 \n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "$$\n",
    "f_1(x)=T_1(x)\n",
    "$$\n",
    "\n",
    "\n",
    "此时残差为$r_{2i}=y_i - f_1(x_i), \\space i=1,2,...,10$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dressed-premises",
   "metadata": {},
   "source": [
    "## 计算残差$r_{2i}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "chinese-perspective",
   "metadata": {},
   "outputs": [],
   "source": [
    "y_bar1 = df['y'][:6]-6.24"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "monthly-christmas",
   "metadata": {},
   "outputs": [],
   "source": [
    "y_bar1 = y_bar1.append(df['y'][6:]-8.91)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "finite-amino",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0   -0.68\n",
       "1   -0.54\n",
       "2   -0.33\n",
       "3    0.16\n",
       "4    0.56\n",
       "5    0.81\n",
       "6   -0.01\n",
       "7   -0.21\n",
       "8    0.09\n",
       "9    0.14\n",
       "Name: y, dtype: float64"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_bar1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "satisfied-adobe",
   "metadata": {},
   "source": [
    "## 计算第二次分割点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "electronic-bubble",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "分割点:1.5, 损失值:1.417822222222222\n",
      "分割点:2.5, 损失值:1.0028874999999997\n",
      "分割点:3.5, 损失值:0.7904666666666667\n",
      "分割点:4.5, 损失值:1.1296750000000004\n",
      "分割点:5.5, 损失值:1.6578400000000002\n",
      "分割点:6.5, 损失值:1.930008333333334\n",
      "分割点:7.5, 损失值:1.9298380952380956\n",
      "分割点:8.5, 损失值:1.8964500000000002\n",
      "分割点:9.5, 损失值:1.9080000000000001\n"
     ]
    }
   ],
   "source": [
    "# 计算所有分割点对应的损失值\n",
    "for i in range(1, 10):\n",
    "    print('分割点:{}, 损失值:{}'.format(i+0.5, ((y_bar1[:i] - y_bar1[:i].mean())**2).sum() + ((y_bar1[i:]-y_bar1[i:].mean())**2).sum()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "cordless-juice",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.9301000000000006"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 此时损失值\n",
    "np.sum((np.array(y_bar1[:6]))**2) + np.sum((np.array(y_bar1[6:]))**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exciting-necklace",
   "metadata": {},
   "source": [
    "\n",
    "第2步求$T_2(x)$，方法和求$T_1(x)$一样，只是拟合的数据是上面的y_bar。\n",
    "经过计算，当x以3.5为分割点时，残差表1中损失值最小，可以得到：\n",
    "$$\n",
    "T_{2}(x) = \\begin{cases}\n",
    "-0.52, &x<3.5 \\\\\n",
    "0.22, &x>=3.5 \n",
    "\\end{cases} \n",
    "$$\n",
    "\n",
    "$$\n",
    "f_2(x) = f_1(x)+T_2(x) = \\begin{cases}\n",
    "5.72, &x<3.5 \\\\\n",
    "6.46, &3.5<=x<6.5 \\\\\n",
    "9.13, &x>=6.5 \n",
    "\\end{cases}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "amended-lancaster",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7905000000000015"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# f2 拟合训练数据时的损失值\n",
    "np.sum((df['y'][:3]-5.72)**2) + np.sum((df['y'][3:6] - 6.46)**2) + np.sum((df['y'][6:] - 9.13)**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "peripheral-architect",
   "metadata": {},
   "source": [
    "## 计算残差$r_{3i}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "through-slovakia",
   "metadata": {},
   "outputs": [],
   "source": [
    "y_bar2 = (df['y'][:3]-5.72).append(df['y'][3:6] - 6.46).append(df['y'][6:] - 9.13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "natural-notion",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0   -0.16\n",
       "1   -0.02\n",
       "2    0.19\n",
       "3   -0.06\n",
       "4    0.34\n",
       "5    0.59\n",
       "6   -0.23\n",
       "7   -0.43\n",
       "8   -0.13\n",
       "9   -0.08\n",
       "Name: y, dtype: float64"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_bar2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "accessory-hazard",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "分割点:1.5, 损失值:0.7616888888888904\n",
      "分割点:2.5, 损失值:0.7697875000000016\n",
      "分割点:3.5, 损失值:0.7904666666666682\n",
      "分割点:4.5, 损失值:0.7892750000000017\n",
      "分割点:5.5, 损失值:0.7580000000000012\n",
      "分割点:6.5, 损失值:0.47220833333333345\n",
      "分割点:7.5, 损失值:0.5936095238095243\n",
      "分割点:8.5, 损失值:0.7624000000000015\n",
      "分割点:9.5, 损失值:0.7832000000000017\n"
     ]
    }
   ],
   "source": [
    "for i in range(1, 10):\n",
    "    print('分割点:{}, 损失值:{}'.format(i+0.5, ((y_bar2[:i] - y_bar2[:i].mean())**2).sum() + ((y_bar2[i:]-y_bar2[i:].mean())**2).sum()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exceptional-phenomenon",
   "metadata": {},
   "source": [
    "继续求得\n",
    "\n",
    "$$\n",
    "T_{3}(x) = \\begin{cases}\n",
    "0.15, &x<6.5 \\\\\n",
    "-0.22, &x>=6.5 \\space\\space\\space L(y, f_3(x)) = 0.47\n",
    "\\end{cases} \n",
    "$$\n",
    "\n",
    "$$\n",
    "f_3(x) = f_2(x)+T_3(x) = \\begin{cases}\n",
    "5.87, &x<3.5 \\\\\n",
    "6.61, &3.5<=x<6.5 \\\\\n",
    "8.91, &x>=6.5 \n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "matched-concrete",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.47230000000000016"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# f3 拟合训练数据时的损失值\n",
    "np.sum((df['y'][:3]-5.87)**2) + np.sum((df['y'][3:6] - 6.61)**2) + np.sum((df['y'][6:] - 8.91)**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "swedish-furniture",
   "metadata": {},
   "source": [
    "$$\n",
    "T_{4}(x) = \\begin{cases}\n",
    "-0.16, &x<4.5 \\\\\n",
    "0.11, &x>=4.5 \\space\\space\\space L(y, f_4(x)) = 0.30\n",
    "\\end{cases} \n",
    "$$\n",
    "\n",
    "$$\n",
    "T_{5}(x) = \\begin{cases}\n",
    "0.07, &x<6.5 \\\\\n",
    "-0.11, &x>=6.5 \\space\\space\\space L(y, f_5(x)) = 0.23\n",
    "\\end{cases} \n",
    "$$\n",
    "\n",
    "$$\n",
    "T_{6}(x) = \\begin{cases}\n",
    "-0.15, &x<2.5 \\\\\n",
    "0.04, &x>=2.5 \n",
    "\\end{cases} \n",
    "$$\n",
    "\n",
    "$$\n",
    "f_6(x) = f_5(x)+T_{6}(x) = T_1(x)+...+T_5(x)+T_6(x)\\\\ \\begin{cases}\n",
    "5.63, &x<2.5 \\\\\n",
    "5.82, &2.5<=x<3.5 \\\\\n",
    "6.56, &3.5<=x<4.5 \\\\\n",
    "6.83, &4.5<=x<5.5 \\\\\n",
    "8.95, &5.5<=x<6.5 \\\\\n",
    "8.95, &x>=6.5 \n",
    "\\end{cases} \n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "tropical-seminar",
   "metadata": {},
   "source": [
    "用$f_6(x)$拟合训练数据集的平方损失误差是：\n",
    "$$\n",
    "L(y, f_6(x)) = \\sum_{i=1}^{10}(y_i - f_6(x_i))^2 = 0.17\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "backed-philadelphia",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "mental-darwin",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "egyptian-respect",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "standing-bleeding",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dominican-perry",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
